1. Field of the Invention
The present invention relates to a motion vector detecting apparatus and a recording medium.
2. Description of the Related Art
In encoding a motion picture signal, a method (interframe coding) of encoding the difference between frames in view of high interframe correlation of a motion picture signal is often used to efficiently compress the information amount. That is, a first frame having no target frame from which the difference is calculated is directly encoded. However, for each frame following the first frame, the difference between the frame and an immediately preceding frame (reference frame) obtained by decoding the encoded information is calculated, and this difference is encoded.
In this method, the information amount can be reduced compared to a method in which all frames are entirely encoded. However, if there is a motion between frames the difference between which is to be calculated, the difference value is sometimes increased. Accordingly, the method cannot be said to be satisfactory in terms of compression of the information amount. To compress the information amount more efficiently by also taking account of these situations, therefore, a method called motion compensation (motion-compensated interframe coding) is used.
In interframe coding using no motion compensation, the difference between frames is calculated in a portion where the two frames to be compared have the same spatial coordinates. When motion compensation is used, on the other hand, it is not always necessary for the spatial coordinates between two frames to be the same. The frame motion is taken into consideration for calculating the difference between the frames with respect to a position in a reference frame to minimize the difference. A motion vector represents a shift of the coordinates of the position in the reference frame where the difference is to be calculated from the coordinates of the coding target position. This will be described below with reference to an accompanying drawing.
FIGS. 3A-3D are views for explaining motion-compensated interframe prediction and a motion vector. In FIGS. 3A-3D, reference numeral 301 denotes a reference frame; 302, a coding target frame in which only a white star .star. moves and the background remains still. The coding target frame 302 is divided into a plurality of small blocks for performing motion-compensated interframe coding in units of blocks.
For example, in ITU-T recommended H. 261 or H. 263 as a moving picture communication coding standard or in MPEG1, MPEG2 or MPEG4 as a moving picture storage coding standard, a frame is encoded by dividing it into 16.times.16-pixel units called macroblocks. Reference numeral 303 denotes the way the coding target frame 302 is divided into a plurality of macroblocks.
Attention is focused on a block 303a, among other macroblocks of the coding target frame 303, where the white star .star. exists. Reference numeral 304 denotes the same reference frame as 301. In the reference frame 304, a block having the same coordinates as the macroblock 303a is a block 304a. However, since there is a motion between these two frames, a block which minimizes the difference from the macroblock 303a is a block 304b. Hence, reference numeral 304c which represents a shift of the coordinates of the block 304b from the coordinates of the block 304a is a motion vector.
The efficiency of information compression is higher when the difference between the macroblock 303a in the coding target frame and the block 304b in the reference frame and the motion vector 304c are encoded than when the difference between the macroblock 303a in the coding target frame and the block 304a in the reference frame is encoded.
One method often used as a method for detecting this motion vector is a block matching method. In this method, a search range within which a motion vector is detected is previously set around the position of a coding target block.
The sum of absolute difference (SAD) between pixels in the coding target block and pixels in each of blocks corresponding to all candidate vectors in this search range is calculated. A candidate block having the minimum sum is bused as a reference block (corresponding to the block 304b in FIG. 3C). This method will be described below with reference to an accompanying drawing.
FIGS. 4A and 4B are views for explaining the block matching method. For the sake of simplicity, it is assumed that a coding target block has 2.times.2 pixels and a search range has +2 pixels in each of upper, lower, left and right directions in addition to the coding target block. In FIG. 4A, reference numeral 401 denotes the position of a coding target block in a coding target frame; 402, a search range in an immediately preceding reference frame; and in FIG. 4B, 403 to 427, blocks corresponding to all candidate vectors in the search range 402. Also, each number in the circles indicates a pixel number.
In this example case, the SAD of pixels in the coding target block 401 and pixels at the corresponding positions in each of the candidate blocks 403 to 427 is calculated. In the case of the upper left candidate block 403, EQU .vertline.a15-b1.vertline.+.vertline.a16-b2.vertline.+.vertline.a21-b7.vert line.+.vertline.a22-b8.vertline.
is calculated. In this expression, a** is the value of a coding target pixel, b** is the value of a reference pixel, and ** corresponds to a pixel number in FIGS. 4A and 4B. A similar operation is performed for the other candidate blocks 404 to 427, and a block having the minimum sum is used as a reference block.
As described above, the compression method using a motion vector also takes account of a faster motion of an image in a frame. Accordingly, to increase the accuracy of motion vector detection, i.e., to detect a reference block which minimizes the SAD of pixels between positions in that block and a coding target block, it is necessary to expand the search range so that a larger number of candidate vectors are included.
When the search range is expanded, however, the motion search operation amount is increased accordingly. This undesirably increases the time required to detect a motion vector.